package sort;

/**
 * 插入排序
 * @author Tang Jiujia
 * @since 10:52 2020-04-14
 */
public class InsertionSort {
    /**
     * 插入排序法
     *
     * @param b 要排序的数组
     * @return void
     */
    public static void insertionSort(int[] b) {
        int n = b.length;
        if (n <= 1) {
            return;
        }
        for (int i = 1; i < n; i++) {
            int value = b[i];
            int j = i - 1;
            //寻找插入位置
            for (; j >= 0; --j) {
                if (b[j] > value) {
                    //移动数据
                    b[j+1] = b[j];
                } else {
                    break;
                }
            }
            //插入数据
            b[j+1] = value;
        }
    }

    public static void main(String[] args) {
        int[] b = {5, 9, 8, 2, 1, 9, 6, 3, 2};
        insertionSort(b);
        for (int value : b) {
            System.out.print(value + " ");
        }
    }
}
